Co-NP - определение. Что такое Co-NP
Diclib.com
Словарь ChatGPT
Введите слово или словосочетание на любом языке 👆
Язык:

Перевод и анализ слов искусственным интеллектом ChatGPT

На этой странице Вы можете получить подробный анализ слова или словосочетания, произведенный с помощью лучшей на сегодняшний день технологии искусственного интеллекта:

  • как употребляется слово
  • частота употребления
  • используется оно чаще в устной или письменной речи
  • варианты перевода слова
  • примеры употребления (несколько фраз с переводом)
  • этимология

Что (кто) такое Co-NP - определение

COMPLEXITY CLASS
CoNP; Co np; Co NP; NP = co-NP problem

NP-hard         
  • P≠NP]], while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)
<complexity> A set or property of computational {search problems}. A problem is NP-hard if solving it in {polynomial time} would make it possible to solve all problems in class NP in polynomial time. Some NP-hard problems are also in NP (these are called "NP-complete"), some are not. If you could reduce an NP problem to an NP-hard problem and then solve it in polynomial time, you could solve all NP problems. See also computational complexity. [Examples?] (1995-04-10)
NP-hardness         
  • P≠NP]], while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)
In computational complexity theory, NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem.

Википедия

Co-NP

In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely if only no-instances have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.

That is, co-NP is the set of decision problems where there exists a polynomial p ( n ) {\displaystyle p(n)} and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by p ( n ) {\displaystyle p(n)} , the Turing machine M accepts the pair (x, c).